/* 

给你一个 n x n 矩阵 matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。

 

示例 1：

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13
解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
示例 2：

输入：matrix = [[-5]], k = 1
输出：-5
 

提示：

n == matrix.length
n == matrix[i].length
1 <= n <= 300
-109 <= matrix[i][j] <= 109
题目数据 保证 matrix 中的所有行和列都按 非递减顺序 排列
1 <= k <= n2

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

*/

// 题解：https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/solution/dui-shu-zhi-er-fen-cha-zhao-by-hyj8/
/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
const countInMatrix = (matrix, midVal) => {
    const n = matrix.length; // 这题是方阵 n行n列
    let count = 0;
    let row = 0; // 第一行
    let col = n - 1; // 最后一列
    while (row < n && col >= 0) {
        if (midVal >= matrix[row][col]) { // 大于等于当前行的最右
            count += col + 1; // 不大于它的数增加col + 1个
            row++; // 比较下一行
        } else { // 干不过当前行的最右元素
            col--; // 留在当前行，比较左边一个
        }
    }
    return count;
};

const kthSmallest = (matrix, k) => {
    const n = matrix.length;
    let low = matrix[0][0];
    let high = matrix[n - 1][n - 1];
    while (low <= high) {
        let midVal = low + ((high - low) >>> 1); // 获取中间值
        let count = countInMatrix(matrix, midVal); // 矩阵中小于等于它的个数
        if (count < k) {
            low = midVal + 1;
        } else {
            high = midVal - 1;
        }
    }
    return low;
};